''' 网址
https://leetcode.cn/problems/rotting-oranges/

思路： 这种需要一圈一圈往外传播的一般用BFS解， 先找到起始所有腐烂的橘子，
然后循环处理，把新腐烂的橘子加入下一次循环的队列中，
当下一次循环的队列为空时，说明不能继续腐烂了，
判断一下还有没有新鲜的橘子，如果有，就返回-1，否则返回分钟数
'''

'''
之所以使用两个队列 rotlist，newrotlist 来做中间变量，
是因为这里一开始不只有一个烂橘子，
也就是不止一个root，
rotlist存储多个root， newrotlist则存储roots往外扩散的新的节点
'''

class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        dx = [1, -1, 0, 0] # 行，纵轴
        dy = [0, 0, 1, -1] # 列，横轴
        rotlist = list()   # 初始队列 -- 初始所有烂橘子
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    rotlist.append([i, j])
        minute = 0
        while (rotlist):  # BFS循环
            newrotlist = list()  # 中介队列 --- 本轮循环所有烂橘子引发的烂橘子
            for rotnode in rotlist:
                x0 = rotnode[0]
                y0 = rotnode[1]

                for k in range(4):  # 以当前点位中心，进行上下左右移动
                    x = x0 + dx[k]  # 纵坐标
                    y = y0 + dy[k]  # 横坐标

                    '''判断是否超出边界，并且是否为好橘子'''
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                        grid[x][y] = 2
                        newrotlist.append([x, y])
            if not newrotlist: # 没有新的烂橘子了，就彻底退出循环
                break

            rotlist = newrotlist[:]  # 把这轮产生的烂橘子作为下一轮循环的起点
            minute += 1

        for row in grid:
            for i in row:
                if i == 1:  # 还有新鲜的
                    return -1
        return minute

grid = [[2,1,1],[1,1,0],[0,1,1]]
s = Solution()
print(s.orangesRotting(grid))



